#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>
#include <limits>

using namespace std;

int maxProfit(vector<int>& prices) 
{
  int ret=0;
  int m = prices.size();
  if(m<2)
  {
    return ret;
  }

  int min = prices[0];
  ret = std::numeric_limits<int>::min();
  for( int i=1;i<m;++i )
  {
    if( prices[i]>prices[i-1] )
    {
     if( (prices[i]-min) > ret )
     {
       ret = prices[i] - min;
     }
    }
    else
    {
      if( prices[i] <min )
      {
        min = prices[i];
      }
    }

  }

  return ret>=0?ret:0;
}



int main(int argc,char *argv[])
{
 
  vector<int> prices={1,5,4,6,2};
  vector<int> prices1={6,5,4,7,2,6,1,4};

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  int ret  = maxProfit( prices1 );

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

  cout<<"ret"<<ret<<endl;



  return 0;
}
